package leetcode.offer;

import leetcode.common.ListNode;

@SuppressWarnings("all")
public class _21_奇数位升序偶数位降序链表排序 {

    public static ListNode orderListNode(ListNode head) {
        if (head == null || head.next == null) return head;
        // 拆分链表
        ListNode[] listNodes = resolutionLists(head);
        // 翻转链表
        ListNode listNode = reverseList(listNodes[1]);
        // 合并链表
        return combineList(listNodes[0], listNode);
    }

    /**
     * 按照奇偶位拆分成两个链表
     */
    public static ListNode[] resolutionLists(ListNode head) {
        // 奇数链表
        ListNode oddNode = new ListNode(0);
        // 偶数链表
        ListNode evenNode = new ListNode(0);

        ListNode oddCur = oddNode;
        ListNode evenCur = evenNode;

        // 判断当前链表是奇数结点还是偶数结点
        int count = 1;
        while (head != null) {
            if ((count & 1) == 1) {
                oddCur.next = head;
                oddCur = oddCur.next;
            } else {
                evenCur.next = head;
                evenCur = evenCur.next;
            }
            head = head.next;
            count++;
        }
        oddCur.next = null;
        evenCur.next = null;
        return new ListNode[]{oddNode.next, evenNode.next};
    }

    /**
     * 反转链表
     */
    public static ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode node = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return node;
    }

    /**
     * 合并两个有序链表
     */
    public static ListNode combineList(ListNode head1, ListNode head2) {
        if (head1 == null) return head2;
        if (head2 == null) return head1;
        ListNode dummyNode = new ListNode(0);
        ListNode node = dummyNode;
        while (head1 != null && head2 != null) {
            if (head1.val <= head2.val) {
                node.next = head1;
                head1 = head1.next;
            } else {
                node.next = head2;
                head2 = head2.next;
            }
            node = node.next;
        }
        node.next = head1 == null ? head2 : head1;
        return dummyNode.next;
    }

    public static void main(String[] args) {
        ListNode head = init();
        head = orderListNode(head);
        while (head != null) {
            System.out.print(head.val + " ");
            head = head.next;
        }
    }

    public static ListNode init() {
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(8);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(6);
        ListNode node5 = new ListNode(5);
        ListNode node6 = new ListNode(4);
        ListNode node7 = new ListNode(7);
        ListNode node8 = new ListNode(2);
        ListNode node9 = new ListNode(9);

        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        node5.next = node6;
        node6.next = node7;
        node7.next = node8;
        node8.next = node9;
        return node1;
    }
}
